//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2002-2007
// (c) Philipp Peshin (phil@mobilae.ru), 2003
//
// Map data handling.
//

# include "StdAfx.h"
# include "Resource.h"
# include "Map.h"
# include "MapView.h"
# include "Types.h"
# include "GarminTypes.h"
# include "Load.h"
# include "Log.h"
# include "Levels.h"
# include "Status.h"
# include "Label.h"
# include "Scale.h"
# include "Transform.h"
# include "STL_helpers.h"
# include "fast_floor.h"
# include "Globals.h"

void map_header_t::clear () {
	strID           = "";
	strName         = "";

	wCodePage       = 0;//::GetACP ();
	CodeSchema      = bpsSBCS;

	ElevationUnits  = unFeet;

	Preprocess      = ppFull;

	cTreSize        = 511;//6000;
	fTreMargin      = 0;//0.02F;
	cRgnLimit       = 127;//700;

	bTransparent    = false;

	bPOIIndex       = true;//false;
	bPOINumberFirst = true;
	bPOIZipFirst    = true;

	bMG             = false;
	bNumbering      = false;
	bRouting        = false;
	bInvisible      = false;
	strCopyright    = "";

	extra.clear ();
}

void map_header_t::swap (map_header_t & _other) {
	std::swap (strID,           _other.strID);
	std::swap (strName,         _other.strName);

	std::swap (wCodePage,       _other.wCodePage);
	std::swap (CodeSchema,      _other.CodeSchema);

	std::swap (ElevationUnits,  _other.ElevationUnits);

	std::swap (Preprocess,      _other.Preprocess);

	std::swap (cTreSize,        _other.cTreSize);
	std::swap (fTreMargin,      _other.fTreMargin);
	std::swap (cRgnLimit,       _other.cRgnLimit);

	std::swap (bTransparent,    _other.bTransparent);
	std::swap (bPOIIndex,       _other.bPOIIndex);
	std::swap (bPOINumberFirst, _other.bPOINumberFirst);
	std::swap (bPOIZipFirst,    _other.bPOIZipFirst);
	std::swap (bMG,             _other.bMG);
	std::swap (bNumbering,      _other.bNumbering);
	std::swap (bRouting,        _other.bRouting);
	std::swap (bInvisible,      _other.bInvisible);
	std::swap (strCopyright,    _other.strCopyright);

	extra.swap (_other.extra);
}

bool map_header_t::operator == (const map_header_t & _other) const {
	return
		strID           == _other.strID &&
		strName         == _other.strName &&

		wCodePage       == _other.wCodePage &&
		CodeSchema      == _other.CodeSchema &&

		ElevationUnits  == _other.ElevationUnits &&

		Preprocess      == _other.Preprocess &&

		cTreSize        == _other.cTreSize &&
		fTreMargin      == _other.fTreMargin &&
		cRgnLimit       == _other.cRgnLimit &&

		bTransparent    == _other.bTransparent &&

		bPOIIndex       == _other.bPOIIndex &&
		bPOINumberFirst == _other.bPOINumberFirst &&
		bPOIZipFirst    == _other.bPOIZipFirst &&

		bMG             == _other.bMG &&
		bNumbering      == _other.bNumbering &&
		bRouting        == _other.bRouting &&
		bInvisible      == _other.bInvisible &&
		strCopyright    == _other.strCopyright;
}

//////////////////////////////////////////////

CCritSec g_cs;
map_t g_map;

void map_t::clear () {
	this->bNoHeader = true;
	this->Header.clear ();
	this->cHeaderLen = 0;

	this->Levels.clear ();

	for (size_t cKind = 0; cKind < rkMax; ++ cKind)
		this->layers [cKind].clear ();

	this->Countries.clear ();
	this->Regions  .clear ();
	this->Cities   .clear ();
	this->Zips     .clear ();
	this->Highways .clear ();

	this->ExtraSections.clear ();

	this->pTypeSet = & g_tsNull;

	for (renderers_t::iterator ir = this->renderers.begin (); ir != this->renderers.end (); ++ ir)
		delete * ir;
	this->renderers     .clear ();
	this->file_refs     .clear ();

	this->rgnodes       .clear ();
	this->rgrestrictions.clear ();

	this->rectBound           = rect_t ();
	this->cMaxPointsInElement = 0;
	this->fCosY               = 1;

	this->pFirstRgn           = NULL;
	this->pLastRgn            = NULL;

	this->cPrecOrder          = 5;

	this->bDirtyRGNodes       = true;
	this->dwMaxNodeID         = 0;
	this->dwMaxRoadID         = 0;
}

map_t & map_t::operator = (const map_t & _other) {
	SetProgressStatus (0);

	const size_t cTotalRgns = _other.GetRgnCount ();
	size_t cRgnsProcessed = 0;

	////////////////////////////////

	clear ();

	this->bNoHeader           = _other.bNoHeader;
	this->cHeaderLen          = _other.cHeaderLen;
	this->Header              = _other.Header;
	this->Levels              = _other.Levels;

	this->ExtraSections       = _other.ExtraSections;

	this->pTypeSet            = _other.pTypeSet;

	this->renderers           = _other.renderers;
	
	this->rectBound           = _other.rectBound;
	this->cMaxPointsInElement = _other.cMaxPointsInElement;
	this->fCosY               = _other.fCosY;
	this->cPrecOrder          = _other.cPrecOrder;

	//
	// Deep copy for pointers.
	//

	// File refs.
	typedef std::map<const file_ref_t *, file_ref_t *> fr2fr_t;
	fr2fr_t fr2fr;
	for (file_refs_t::const_iterator fi = _other.file_refs.begin (); fi != _other.file_refs.end (); ++ fi) {
		const file_ref_t & fr = * fi;
		this->file_refs.push_back (fr);
		fr2fr [& fr] = & this->file_refs.back ();
	}

	// Countries.
	typedef std::map<const country_t *, country_t *> ctry2ctry_t;
	ctry2ctry_t ctry2ctry;
	for (countries_t::const_iterator cyi = _other.Countries.begin (); cyi != _other.Countries.end (); ++ cyi) {
		const country_t & country = * cyi;
		this->Countries.push_back (country);
		ctry2ctry [& country] = & this->Countries.back ();
	}

	// Regions.
	typedef std::map<const region_t *, region_t *> region2region_t;
	region2region_t region2region;
	for (regions_t::const_iterator ri = _other.Regions.begin (); ri != _other.Regions.end (); ++ ri) {
		const region_t & region = * ri;
		this->Regions.push_back (region);
		if (region.pCountry) {
			const ctry2ctry_t::iterator i = ctry2ctry.find (region.pCountry);
			assert (i != ctry2ctry.end ());
			this->Regions.back ().pCountry = i == ctry2ctry.end () ? NULL : i->second;
		}
		region2region [& region] = & this->Regions.back ();
	}

	// Cities.
	typedef std::map<const city_t *, city_t *> city2city_t;
	city2city_t city2city;
	for (cities_t::const_iterator cti = _other.Cities.begin (); cti != _other.Cities.end (); ++ cti) {
		const city_t & city = * cti;
		this->Cities.push_back (city);
		if (city.pRegion) {
			const region2region_t::iterator i = region2region.find (city.pRegion);
			assert (i != region2region.end ());
			this->Cities.back ().pRegion = i == region2region.end () ? NULL : i->second;
		}
		city2city [& city] = & this->Cities.back ();
	}

	// Zips.
	typedef std::map<const zip_t *, zip_t *> zip2zip_t;
	zip2zip_t zip2zip;
	for (zips_t::const_iterator zi = _other.Zips.begin (); zi != _other.Zips.end (); ++ zi) {
		const zip_t & zip = * zi;
		if (zip.bDeleted)
			continue;
		this->Zips.push_back (zip);
		zip2zip [& zip] = & this->Zips.back ();
	}

	// Highways.
	typedef std::map<const highway_t *, highway_t *> hw2hw_t;
	hw2hw_t hw2hw;
	for (highways_t::const_iterator hi = _other.Highways.begin (); hi != _other.Highways.end (); ++ hi) {
		const highway_t & highway = * hi;
		this->Highways.push_back (highway);
		if (highway.pRegion) {
			const region2region_t::iterator i = region2region.find (highway.pRegion);
			assert (i != region2region.end ());
			this->Highways.back ().pRegion = i == region2region.end () ? NULL : i->second;
		}
		hw2hw [& highway] = & this->Highways.back ();
	}

	// Routing graph.
	const_cast<map_t &> (_other).CountRGNodes ();

	rgrestrictions_t::const_iterator r;
	for (r = _other.rgrestrictions.begin (); r != _other.rgrestrictions.end (); ++ r) {
		const rgrestriction_t & restrictionOther = r->second;
		rgnode_t * const pNodeOther = restrictionOther.pNode;
		if (pNodeOther)
			pNodeOther->pExtra = NULL;
	}

	typedef std::map<const rgnode_t *, rgnode_t *> rgnode2rgnode_t;
	rgnode2rgnode_t rgnode2rgnode;
	this->rgnodes.clear ();
	for (rgnodes_t::const_iterator ni = _other.rgnodes.begin (); ni != _other.rgnodes.end (); ++ ni) {
		const rgnode_t & nodeOther = * ni;
		nodeOther.pExtra = (void *) nodeOther.IsUsed ();
		if (! nodeOther.IsUsed ())
			continue;

		rgnode_t & nodeNew = CreateNode (nodeOther.dwNodeID);
		nodeNew = nodeOther;
		nodeNew.btPolylines   = 0;
		nodeNew.btCardinality = 0;

		rgnode2rgnode [& nodeOther] = & nodeNew;
	}

	this->bDirtyRGNodes = true;
	this->dwMaxNodeID = _other.dwMaxNodeID;
	this->dwMaxRoadID = _other.dwMaxRoadID;

	//
	// Copy objects.
	//
	typedef std::map<const rgn_t *, rgn_t *> rgn2rgn_t;
	rgn2rgn_t Roads;
	rgn2rgn_t Waypoints;
	for (rgn_t * pRgnOther = _other.pFirstRgn; pRgnOther; pRgnOther = pRgnOther->pNextRgn) {
		rgn_t & rgnOther = * pRgnOther;
		if (rgnOther.IsDeleted ())
			continue;

		//
		// Create rgn's copy.
		//
		rgn_t & rgn = this->CreateRgn ((RGN_KIND) rgnOther.Kind);
		rgn.pTypeDesc       = rgnOther.pTypeDesc;
		rgn.ushType         = rgnOther.ushType;
		rgn.Kind            = rgnOther.Kind;
		rgn.dwFlags         = rgnOther.dwFlags;
		rgn.strLabel        = rgnOther.strLabel;
		rgn.ptLabel         = rgnOther.ptLabel;
		rgn.chLabelAngle    = rgnOther.chLabelAngle;
		rgn.ucLabelWidthBy8 = rgnOther.ucLabelWidthBy8;
		rgn.ucLabelHeight   = rgnOther.ucLabelHeight;
		rgn.uchEndLevel     = rgnOther.uchEndLevel;
		rgn.elements        = rgnOther.elements;
		rgn.origins         = rgnOther.origins;
		rgn.strComment      = rgnOther.strComment;
		rgn.pExtra          = rgnOther.pExtra;
		rgn.rectBound       = rgnOther.rectBound;
		rgn.fSize2          = rgnOther.fSize2;
		rgn.fAveElementArea = rgnOther.fAveElementArea;
		rgn.cBeginPos       = rgnOther.cBeginPos;
		rgn.cEndPos         = rgnOther.cEndPos;
		rgn.cFileLine       = rgnOther.cFileLine;
		rgn.ucExtendedFlags = rgnOther.ucExtendedFlags;

		//
		// Deep copy for pointers.
		//

		// pFileRef.
		if (rgnOther.pFileRef) {
			const fr2fr_t::iterator i = fr2fr.find (rgnOther.pFileRef);
			assert (i != fr2fr.end ());
			rgn.pFileRef = i == fr2fr.end () ? NULL : i->second;
		} else
			rgn.pFileRef = NULL;

		if (rgnOther.pExtra) {
			// pExtra->pCity.
			if (rgnOther.pExtra->pCity) {
				const city2city_t::iterator i = city2city.find (rgnOther.pExtra->pCity);
				assert (i != city2city.end ());
				rgn.pExtra->pCity = i == city2city.end () ? NULL : i->second;
			}

			// pExtra->pZip.
			if (rgnOther.pExtra->pZip) {
				const zip2zip_t::iterator i = zip2zip.find (rgnOther.pExtra->pZip);
				assert (i != zip2zip.end ());
				rgn.pExtra->pZip = i == zip2zip.end () ? NULL : i->second;
			}

			// pExtra->pHighway.
			if (rgnOther.pExtra->pHighway) {
				const hw2hw_t::iterator i = hw2hw.find (rgnOther.pExtra->pHighway);
				assert (i != hw2hw.end ());
				rgn.pExtra->pHighway = i == hw2hw.end () ? NULL : i->second;
			}
		}

		// elements [].pExtra->PointExtras.
		const size_t cElements = rgnOther.elements.size ();
		for (size_t cElement = 0; cElement < cElements; ++ cElement) {
			const rgn_element_t & elementOther = rgnOther.elements [cElement];
			if (elementOther.bDeleted || ! elementOther.pExtra)
				continue;
			rgn_element_t & elementThis = rgn.elements [cElement];
			const size_t cPoints = elementThis.points.size ();

			const point_extras_t & PointExtrasOther = elementOther.pExtra->PointExtras;
				  point_extras_t & PointExtrasThis  = elementThis .pExtra->PointExtras;
			const size_t cNodes = PointExtrasOther.size ();
			assert (PointExtrasThis.size () == cNodes);

			if (cNodes != 0) {
				for (size_t cNode = 0; cNode < cNodes; ++ cNode) {
					const rgnode_t * const pNodeOther = PointExtrasOther [cNode].GetRGNode ();
					if (pNodeOther != NULL) {
						const rgnode2rgnode_t::iterator i = rgnode2rgnode.find (pNodeOther);
						assert (i != rgnode2rgnode.end ());

						PointExtrasThis [cNode].SetRGNode (i != rgnode2rgnode.end () ? i->second : NULL, cNode, cPoints);
					}

					const numbers_t & NumbersOther = PointExtrasOther [cNode].Numbers;
					if (NumbersOther.bHasNumbers) {
						numbers_t & NumbersThis = PointExtrasThis [cNode].Numbers;
						NumbersThis = NumbersOther;

						if (NumbersOther.pZipLeftAfter) {
							const zip2zip_t::iterator iZipLeft = zip2zip.find (NumbersOther.pZipLeftAfter);
							assert (iZipLeft != zip2zip.end ());
							NumbersThis.pZipLeftAfter = iZipLeft != zip2zip.end () ? iZipLeft->second : NULL;
						}
						if (NumbersOther.pZipRightAfter) {
							const zip2zip_t::iterator iZipRight = zip2zip.find (NumbersOther.pZipRightAfter);
							assert (iZipRight != zip2zip.end ());
							NumbersThis.pZipRightAfter = iZipRight != zip2zip.end () ? iZipRight->second : NULL;
						}

						if (NumbersOther.pCityLeftAfter) {
							const city2city_t::iterator iCityLeft = city2city.find (NumbersOther.pCityLeftAfter);
							assert (iCityLeft != city2city.end ());
							NumbersThis.pCityLeftAfter = iCityLeft != city2city.end () ? iCityLeft->second : NULL;
						}
						if (NumbersOther.pCityRightAfter) {
							const city2city_t::iterator iCityRight = city2city.find (NumbersOther.pCityRightAfter);
							assert (iCityRight != city2city.end ());
							NumbersThis.pCityRightAfter = iCityRight != city2city.end () ? iCityRight->second : NULL;
						}
					}
				}

				Roads [& rgnOther] = & rgn;
			}
		}

		if (rgn.IsWaypoint ())
			// NOTE: this is required for deep copy of routes.
			Waypoints [& rgnOther] = & rgn;

		++ cRgnsProcessed;
		SetProgressStatus (cRgnsProcessed*100/cTotalRgns);
	}

	this->RefreshDrawOrder ();

	// Turn restrictions.
	this->rgrestrictions.clear ();
	for (r = _other.rgrestrictions.begin (); r != _other.rgrestrictions.end (); ++ r) {
		const rgrestriction_t & restrictionOther = r->second;

		rgnode_t * const pNodeOther = restrictionOther.pNode;
		if (pNodeOther == NULL || pNodeOther->pExtra == NULL)
			continue;
		const rgnode2rgnode_t::iterator i = rgnode2rgnode.find (pNodeOther);
		assert (i != rgnode2rgnode.end ());
		if (i == rgnode2rgnode.end ())
			continue;
		rgnode_t * const pNodeNew = i->second;

		rgrestriction_t & restrictionNew = AddRGNodeRestriction (* this, pNodeNew);

		const rgn2rgn_t::const_iterator rf = Roads.find (restrictionOther.pFromRoad);
		restrictionNew.pFromRoad = rf == Roads.end () ? NULL : rf->second;

		const rgn2rgn_t::const_iterator rt = Roads.find (restrictionOther.pToRoad);
		restrictionNew.pToRoad   = rt == Roads.end () ? NULL : rt->second;

		restrictionNew.bFromDirection = restrictionOther.bFromDirection;
		restrictionNew.bToDirection   = restrictionOther.bToDirection;
	}

	// Routes.
	rgns_t & polylines = this->layers [rkPolyline].rgns;
	for (rgns_t::iterator iRgn = polylines.begin (); iRgn != polylines.end (); ++ iRgn) {
		rgn_t & rgn = * iRgn;
		if (rgn.IsRoute ()) {
			route_info_t * const pRoute = rgn.pExtra->wtr.route ();
			const size_t cPoints = pRoute->points.size ();
			for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
				// Deep copy of waypoints refs.
				const rgn_t * const pWptOld = pRoute->points [cPoint].pWaypoint;
				if (pWptOld != NULL) {
					const rgn2rgn_t::const_iterator w = Waypoints.find (pWptOld);
					rgn_t * const pWptNew = w == Waypoints.end () ? NULL : w->second;
					pRoute->points [cPoint].pWaypoint = pWptNew;
				}
			}
		}
	}

	bDirtyRGNodes = true;

	return * this;
}

void map_t::swap (map_t & _other) {
	std::swap (this->cHeaderLen, _other.cHeaderLen);
	this->Header   .swap (_other.Header);
	this->Levels   .swap (_other.Levels);
	this->Countries.swap (_other.Countries);
	this->Regions  .swap (_other.Regions);
	this->Cities   .swap (_other.Cities);
	this->Zips     .swap (_other.Zips);
	this->Highways .swap (_other.Highways);

	this->ExtraSections.swap (_other.ExtraSections);

	std::swap (this->pTypeSet, _other.pTypeSet);

	for (size_t cKind = 0; cKind < rkMax; ++ cKind)
		this->layers [cKind].swap (_other.layers [cKind]);

	this->renderers.swap (_other.renderers);
	this->file_refs.swap (_other.file_refs);
	std::swap (this->bNoHeader, _other.bNoHeader);

	this->rgnodes       .swap (_other.rgnodes);
	this->rgrestrictions.swap (_other.rgrestrictions);

	this->rectBound.swap (_other.rectBound);

	std::swap (this->cMaxPointsInElement, _other.cMaxPointsInElement);
	std::swap (this->fCosY,         _other.fCosY);

	std::swap (this->pFirstRgn,     _other.pFirstRgn);
	std::swap (this->pLastRgn,      _other.pLastRgn);

	std::swap (this->cPrecOrder,    _other.cPrecOrder);

	std::swap (this->bDirtyRGNodes, _other.bDirtyRGNodes);
	std::swap (this->dwMaxNodeID,   _other.dwMaxNodeID);
	std::swap (this->dwMaxRoadID,   _other.dwMaxRoadID);
}

////////////////////////////////////////////////////////////

void map_t::_UpdateLevels (const std::vector<size_t> & _Old2New) {
	for (size_t cKind = 0; cKind < rkMax; ++ cKind) {
		rgns_t & rgns = this->layers [cKind].rgns;

		for (rgns_t::iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			rgn_t & rgn = * iRgn;

			const size_t cElements = rgn.elements.size ();
			for (size_t cElement = 0; cElement < cElements; ++ cElement) {
				rgn_element_t & element = rgn.elements [cElement];
				element.cLevel = _Old2New [element.cLevel];
			}

			const size_t cOrigins = rgn.origins.size ();
			for (size_t cOrigin = 0; cOrigin < cOrigins; ++ cOrigin) {
				rgn_origin_t & origin = rgn.origins [cOrigin];
				origin.cLevel = _Old2New [origin.cLevel];
			}
		}
	}
}

void map_t::_MakeLevelsEqual (map_t & _map1, map_t & _map2) {
	map_levels_t & Levels1 = _map1.Levels;
	const size_t cLevels1 = Levels1.size ();
	size_t c1 = 0;

	map_levels_t & Levels2 = _map2.Levels;
	const size_t cLevels2 = Levels2.size ();
	size_t c2 = 0;

	map_levels_t NewLevels;
	size_t cNew = 0;

	std::vector<size_t> Old2New1 (cLevels1);
	std::vector<size_t> Old2New2 (cLevels2);

	while (c1 < cLevels1 && c2 < cLevels2) {
		const map_level_t & Level1 = Levels1 [c1];
		const map_level_t & Level2 = Levels2 [c2];
		if (Level1.btBits == Level2.btBits) {
			NewLevels.push_back (Level1);
			NewLevels.back ().cZoom = __min (Level1.cZoom, Level2.cZoom);
			Old2New1 [c1 ++] = cNew;
			Old2New2 [c2 ++] = cNew;
		} else if (Level1.btBits < Level2.btBits) {
			NewLevels.push_back (Level2);
			Old2New2 [c2 ++] = cNew;
		} else {
			NewLevels.push_back (Level1);
			Old2New1 [c1 ++] = cNew;
		}
		++ cNew;
	}
	while (c1 < cLevels1) {
		NewLevels.push_back (Levels1 [c1]);
		Old2New1 [c1 ++] = cNew ++;
	}
	while (c2 < cLevels2) {
		NewLevels.push_back (Levels2 [c2]);
		Old2New2 [c2 ++] = cNew ++;
	}

	_map1.Levels = NewLevels;
	_map1._UpdateLevels (Old2New1);

	_map2.Levels = NewLevels;
	_map2._UpdateLevels (Old2New2);
}

struct pa_key_t {
	pa_item_t * pParent;
	const char * strName;

	pa_key_t (pa_item_t * _pParent, const char * _strName) :
		pParent (_pParent), strName (_strName)
	{}

	bool operator < (const pa_key_t & _other) const {
		if (pParent != _other.pParent)
			return pParent < _other.pParent;
		return ::strcmp (strName, _other.strName) < 0;
	}
};

void map_t::RemovePAIDuplicates () {
	typedef std::map<pa_item_t *, pa_item_t *> pai2pai_t;
	typedef std::map<pa_key_t, pa_item_t *> key2pai_t;

	//
	// Remove duplicated countries.
	//
	std::vector<pa_item_t *> vecItemsToDelete;
	{
		// Prepare country-to-country replacement table.
		pai2pai_t country2country;

		key2pai_t key2country;
		for (countries_t::iterator ci = Countries.begin (); ci != Countries.end (); ++ ci) {
			country_t & country = * ci;
			if (country.IsDeleted ())
				continue;

			// Find duplicate.
			const pa_key_t pak (NULL, country.strName.c_str ());
			const key2pai_t::iterator i = key2country.find (pak);
			if (i == key2country.end ()) {
				key2country.insert (key2pai_t::value_type (pak, & country));
			} else {
				country2country [& country] = i->second;
				vecItemsToDelete.push_back (& country);
			}
		}

		if (! country2country.empty ()) {
			// Update region->country refs.
			for (regions_t::iterator ri = Regions.begin (); ri != Regions.end (); ++ ri) {
				region_t & region = * ri;
				if (region.IsDeleted ())
					continue;

				const pai2pai_t::iterator i = country2country.find (region.pCountry);
				if (i != country2country.end ())
					region.pCountry = static_cast<country_t *> (i->second);
			}
		}
	}

	//
	// Remove duplicated regions.
	//
	{
		// Prepare region-to-region replacement table.
		pai2pai_t region2region;

		key2pai_t key2region;
		for (regions_t::iterator ri = Regions.begin (); ri != Regions.end (); ++ ri) {
			region_t & region = * ri;
			if (region.IsDeleted ())
				continue;

			// Find duplicate.
			const pa_key_t pak (region.pCountry, region.strName.c_str ());
			const key2pai_t::iterator i = key2region.find (pak);
			if (i == key2region.end ()) {
				key2region.insert (key2pai_t::value_type (pak, & region));
			} else {
				region2region [& region] = i->second;
				vecItemsToDelete.push_back (& region);
			}
		}

		if (! region2region.empty ()) {
			// Update city->region refs.
			for (cities_t::iterator cti = Cities.begin (); cti != Cities.end (); ++ cti) {
				city_t & city = * cti;
				if (city.IsDeleted ())
					continue;

				const pai2pai_t::iterator i = region2region.find (city.pRegion);
				if (i != region2region.end ())
					city.pRegion = static_cast<region_t *> (i->second);
			}

			// Update highway->region refs.
			for (highways_t::iterator hwi = Highways.begin (); hwi != Highways.end (); ++ hwi) {
				highway_t & highway = * hwi;
				if (highway.IsDeleted ())
					continue;

				const pai2pai_t::iterator i = region2region.find (highway.pRegion);
				if (i != region2region.end ())
					highway.pRegion = static_cast<region_t *> (i->second);
			}
		}
	}

	//
	// Find and remove city duplicates.
	//
	pai2pai_t city2city;
	{
		key2pai_t key2city;
		for (cities_t::iterator cti = Cities.begin (); cti != Cities.end (); ++ cti) {
			city_t & city = * cti;
			if (city.IsDeleted ())
				continue;

			const pa_key_t pak (city.pRegion, city.strName.c_str ());
			const key2pai_t::iterator i = key2city.find (pak);
			if (i == key2city.end ()) {
				key2city.insert (key2pai_t::value_type (pak, & city));
			} else {
				city2city [& city] = i->second;
				city.bDeleted = true;
			}
		}
	}

	//
	// Find and remove highway duplicates.
	//
	pai2pai_t highway2highway;
	{
		key2pai_t key2highway;
		for (highways_t::iterator hwi = Highways.begin (); hwi != Highways.end (); ++ hwi) {
			highway_t & highway = * hwi;
			if (highway.IsDeleted ())
				continue;

			const pa_key_t pak (highway.pRegion, highway.strName.c_str ());
			const key2pai_t::iterator i = key2highway.find (pak);
			if (i == key2highway.end ()) {
				key2highway.insert (key2pai_t::value_type (pak, & highway));
			} else {
				highway2highway [& highway] = i->second;
				highway.bDeleted = true;
			}
		}
	}

	//
	// Find and remove zip code duplicates.
	//
	pai2pai_t zip2zip;
	{
		key2pai_t key2zip;
		for (zips_t::iterator zi = Zips.begin (); zi != Zips.end (); ++ zi) {
			zip_t & zip = * zi;
			if (zip.IsDeleted ())
				continue;

			const pa_key_t pak (NULL, zip.strName.c_str ());
			const key2pai_t::iterator i = key2zip.find (pak);
			if (i == key2zip.end ()) {
				key2zip.insert (key2pai_t::value_type (pak, & zip));
			} else {
				zip2zip [& zip] = i->second;
				zip.bDeleted = true;
			}
		}
	}

	if (! city2city.empty () || ! highway2highway.empty () || ! zip2zip.empty ()) {
		//
		// Update object->city and object->zip refs.
		//

		for (size_t cKind = 0; cKind < rkMax; ++ cKind) {
			rgns_t & rgns = layers [cKind].rgns;

			for (rgns_t::iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
				rgn_t & rgn = * iRgn;
				if (rgn.IsDeleted ())
					continue;

				if (rgn.pExtra) {
					if (rgn.pExtra->pCity) {
						const pai2pai_t::iterator i = city2city.find (rgn.pExtra->pCity);
						if (i != city2city.end ())
							rgn.pExtra->pCity = static_cast<city_t *> (i->second);
					}
					if (rgn.pExtra->pHighway) {
						const pai2pai_t::iterator i = highway2highway.find (rgn.pExtra->pHighway);
						if (i != highway2highway.end ())
							rgn.pExtra->pHighway = static_cast<highway_t *> (i->second);
					}
					if (rgn.pExtra->pZip) {
						const pai2pai_t::iterator i = zip2zip.find (rgn.pExtra->pZip);
						if (i != zip2zip.end ())
							rgn.pExtra->pZip = static_cast<zip_t *> (i->second);
					}
				}

				const size_t cElements = rgn.elements.size ();
				for (size_t cElement = 0; cElement < cElements; ++ cElement) {
					rgn_element_t & element = rgn.elements [cElement];
					if (element.bDeleted || ! element.pExtra)
						continue;

					point_extras_t & PointExtras = element.pExtra->PointExtras;
					const size_t cNodes = PointExtras.size ();

					for (size_t cNode = 0; cNode < cNodes; ++ cNode) {
						numbers_t & Numbers = PointExtras [cNode].Numbers;

						if (Numbers.pZipLeftAfter) {
							const pai2pai_t::iterator iZipLeft = zip2zip.find (Numbers.pZipLeftAfter);
							if (iZipLeft != zip2zip.end ())
								Numbers.pZipLeftAfter = static_cast<zip_t *> (iZipLeft->second);
						}
						if (Numbers.pZipRightAfter) {
							const pai2pai_t::iterator iZipRight = zip2zip.find (Numbers.pZipRightAfter);
							if (iZipRight != zip2zip.end ())
								Numbers.pZipRightAfter = static_cast<zip_t *> (iZipRight->second);
						}

						if (Numbers.pCityLeftAfter) {
							const pai2pai_t::iterator iCityLeft = city2city.find (Numbers.pCityLeftAfter);
							if (iCityLeft != city2city.end ())
								Numbers.pCityLeftAfter = static_cast<city_t *> (iCityLeft->second);
						}
						if (Numbers.pCityRightAfter) {
							const pai2pai_t::iterator iCityRight = city2city.find (Numbers.pCityRightAfter);
							if (iCityRight != city2city.end ())
								Numbers.pCityRightAfter = static_cast<city_t *> (iCityRight->second);
						}
					}
				}
			}
		}
	}

	//
	// Remove the duplicated items previously marked to be deleted.
	//
	const size_t cItemsToDelete = vecItemsToDelete.size ();
	for (size_t c = 0; c < cItemsToDelete; ++ c)
		vecItemsToDelete [c]->bDeleted = true;
}

bool map_t::_HasTextualData () const {
	for (size_t cKind = 0; cKind < rkMax; ++ cKind) {
		const rgns_t & rgns = this->layers [cKind].rgns;

		for (rgns_t::const_iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			const rgn_t & rgn = * iRgn;

			if (! rgn.strLabel.empty () || ! rgn.strComment.empty ())
				return true;
		}
	}

	return false;
}

void map_t::Join (map_t & _other) {
	//
	// Join header data.
	//

	if (! _other.bNoHeader) {
		if (bNoHeader) {
			Levels.swap (_other.Levels);

			cHeaderLen = _other.cHeaderLen;
			Header.swap (_other.Header);
		} else {
			// NOTE: both maps have headers.
			if (Levels != _other.Levels && ! _other.Levels.empty ())
				_MakeLevelsEqual (* this, _other);

			const bool bOther_HasTextualData = _other._HasTextualData ();
			if (bOther_HasTextualData) {
				if (Header.wCodePage != _other.Header.wCodePage) {
					if (Header.wCodePage == 0)
						Header.wCodePage = _other.Header.wCodePage;
				}
				if (Header.CodeSchema != _other.Header.CodeSchema) {
					if (Header.CodeSchema == bpsAscii7)
						Header.CodeSchema = _other.Header.CodeSchema;
				}
			}
/*
			if (Header.cRgnLimit < _other.Header.cRgnLimit)
				Header.cRgnLimit = _other.Header.cRgnLimit;
			if (Header.cTreSize < _other.Header.cTreSize)
				Header.cTreSize = _other.Header.cTreSize;
			if (Header.fTreMargin < _other.Header.fTreMargin)
				Header.fTreMargin = _other.Header.fTreMargin;
*/

			//
			// TODO: join elevation units.
			//

			//
			// Join transparency.
			//
			if (Header.bTransparent)
				Header.bTransparent = _other.Header.bTransparent;

			//
			// Join copyright data.
			//
			if (Header.strCopyright.empty ())
				Header.strCopyright = _other.Header.strCopyright;

			// TODO: join headers.
		}
		bNoHeader = bNoHeader && _other.bNoHeader;
	}

	// Join external nodes.
	{
		layer_t & layer = _other.layers [rkPolyline];
		for (rgns_t::iterator ri = layer.rgns.begin (); ri != layer.rgns.end (); ++ ri) {
			rgn_t & rgn = * ri;
			for (rgn_elements_t::iterator ei = rgn.elements.begin (); ei != rgn.elements.end (); ++ ei) {
				rgn_element_t & element = * ei;
				if (! element.pExtra)
					continue;
				point_extras_t & extras = element.pExtra->PointExtras;
				if (extras.empty ())
					continue;
				const points_t & points = element.points;
				const size_t cPoints = points.size ();
				const size_t cNodes = __min (cPoints, extras.size ());
				for (size_t cPoint = 0; cPoint < cNodes; ++ cPoint) {
					const rgnode_t * const pRGNode = extras [cPoint].GetRGNode ();
					if (pRGNode == NULL)
						continue;
					if (! pRGNode->bIsExternal)
						continue;

					const point_t & point = points [cPoint];
					rgnode_t * const pRGNode2 = FindExternalNode (point);
					if (pRGNode2 != NULL)
						extras [cPoint].SetRGNode (pRGNode2, cPoint, cPoints);
				}
			}
		}
	}

	//
	// Unify type sets.
	//

	if (this->pTypeSet == & g_tsNull) {
		this->pTypeSet = _other.pTypeSet;
	} else {
		if (this->pTypeSet != _other.pTypeSet && _other.pTypeSet != & g_tsNull) {
			const pfConvertTypeSet_t pfConvertTypeSet = _other.pTypeSet->FindConvertTypeSetTo (this->pTypeSet);
			for (rgn_t * pRgnOther = _other.pFirstRgn; pRgnOther; pRgnOther = pRgnOther->pNextRgn) {
				rgn_t & rgnOther = * pRgnOther;
				if (rgnOther.IsDeleted () || rgnOther.IsTrack () || rgnOther.IsRoute ())
					continue;

				rgnOther.SetType (
					this->pTypeSet,
					pfConvertTypeSet (static_cast<RGN_KIND> (rgnOther.Kind), rgnOther.ushType),
					static_cast<RGN_KIND> (rgnOther.Kind)
				);
			}
		}
	}

	//
	// Join layers.
	//

	for (size_t cKind = 0; cKind < rkMax; ++ cKind) {
		rgns_t & rgns = layers [cKind].rgns;
		if (rgns.empty ()) {
			layers [cKind].swap (_other.layers [cKind]);
		} else {
			rgns.splice (rgns.begin (), _other.layers [cKind].rgns);

			layers [cKind].cRgns += _other.layers [cKind].cRgns;
			assert (layers [cKind].cRgns == layers [cKind].rgns.size ());
			_other.layers [cKind].cRgns = 0;

			layers [cKind].cDeletedRgns += _other.layers [cKind].cDeletedRgns;
			_other.layers [cKind].cDeletedRgns = 0;

			if (cKind == rkPolygon)
				RefreshDrawOrder ();
		}
	}

	//
	// Join find nodes.
	//

	JoinLists (Countries, _other.Countries);
	JoinLists (Regions,   _other.Regions);
	JoinLists (Cities,    _other.Cities);
	JoinLists (Zips,      _other.Zips);
	JoinLists (Highways,  _other.Highways);

	RemovePAIDuplicates ();

	//
	// Join extra sections.
	//

	JoinLists (ExtraSections, _other.ExtraSections);

	//
	// TODO: join pTypeSet.
	//
	if (pTypeSet == & g_tsNull)
		pTypeSet = _other.pTypeSet; 

	//
	// Join images.
	//

	JoinRenderers (renderers, _other.renderers);

	//
	// Join attachments.
	//

	JoinLists (file_refs, _other.file_refs);

	//
	// Join routing graphs.
	//

	JoinLists     (rgnodes,        _other.rgnodes);
	JoinMultimaps (rgrestrictions, _other.rgrestrictions);

	CountRGNodes ();
	MakeSureAllNodeIDsAreUnique ();
	MakeSureAllRoadIDsAreUnique ();
	bDirtyRGNodes = true;

	//
	// Join other attributes.
	//

	// Extend rectBound.
	rectBound.Extend (_other.rectBound);

	if (cMaxPointsInElement < _other.cMaxPointsInElement)
		cMaxPointsInElement = _other.cMaxPointsInElement;

	fCosY = ::cos (rectBound.MeanY ()*c_PI/180.f);

	//
	// Splice the load lists.
	//

	SpliceSaveLists (_other);

	if (cPrecOrder < _other.cPrecOrder)
		cPrecOrder = _other.cPrecOrder;
}

size_t map_t::occupied () const {
	size_t ret = 0;

	for (size_t cKind = 0; cKind < rkMax; ++ cKind) {
		const layer_t & layer = this->layers [cKind];
		const rgns_t & rgns = layer.rgns;
		for (rgns_t::const_iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			const rgn_t & rgn = * iRgn;
			if (rgn.IsDeleted ())
				continue;

			ret += sizeof (rgn);
			ret += rgn.strLabel.size ()*sizeof (char);
			ret += rgn.strComment.size ()*sizeof (char);
			if (rgn.pExtra) {
				ret += sizeof (rgn_extra_t);
				ret += rgn.pExtra->strExtra.size ()*sizeof (char);
			}

			const rgn_elements_t & elements = rgn.elements;
			const size_t cElements = elements.size ();
			for (size_t cElement = 0; cElement < cElements; ++ cElement) {
				const rgn_element_t & element = elements [cElement];

				ret += sizeof (rgn_element_t);
				ret += element.points.size ()*sizeof (point_t);
			}

			ret += rgn.origins.size ()*sizeof (rgn_origin_t);
		}
	}

	// TODO: cities/etc
	// TODO: take extra sections into account.

	return ret;
}

rgn_t & map_t::CreateRgn (RGN_KIND _Kind) {
	layer_t & layer = layers [_Kind];

	layer.rgns.push_back (rgn_t ());
	++ layer.cRgns;
	rgn_t & rgn = layer.rgns.back ();

	InsertRgnToSaveList (rgn);

	rgn.cBeginPos = -1;
	rgn.cEndPos   = -1;
	rgn.cFileLine = -1;
//	rgn.cOrdinal  = -1;
	rgn.pFileRef  = NULL;

	return rgn;
}

rgns_t::iterator map_t::CreateRgnIt (RGN_KIND _Kind) {
	layer_t & layer = layers [_Kind];

	const rgns_t::iterator iRgn = layer.rgns.insert (layer.rgns.end (), rgn_t ());
	++ layer.cRgns;

	InsertRgnToSaveList (* iRgn);

	return iRgn;
}

/*
struct CompareRgnArea {
	bool operator () (const rgn_t & _1, const rgn_t & _2) const {
		return _1.fAveElementArea > _2.fAveElementArea;
	}
};*/

LoadStatus_t map_t::LoadMap (const char * _pData, size_t _cFileSize, const char * _strFileName, CMapLoader * _pLoader) {
	clear ();

	//
	// Load the map.
	//

	SetStatus (GetStr (IDS_STATUS_LOADING));
	SetProgressStatus (0);

	assert (_pLoader);
	const LoadStatus_t ls = _pLoader->Load (_pData, _cFileSize, _strFileName, this);
	if (ls != lsOK)
		return ls;

	//
	// Post-process the map.
	//

	SetStatus (GetStr (IDS_STATUS_ANALYZING));
	SetProgressStatus (50);

	bool * const pbRgnsInLevel = reinterpret_cast<bool *> (::alloca (sizeof (bool)*Levels.size ()));
	size_t cLevel;
	for (cLevel = 0; cLevel < Levels.size (); ++ cLevel)
		pbRgnsInLevel [cLevel] = false;

	bool bThereAreHoles = false;

	const size_t cTotalRgns = GetRgnCount ();
//	if (cTotalRgns > 65535)
//		ReportWarning ("Number of objects exceeds 65536 (this is cGPSmapper.exe limitation).");

	size_t cRgnsProcessed = 0;
	for (size_t cKind = 0; cKind < rkMax; ++ cKind) {
		layer_t & layer = layers [cKind];
		rgns_t & rgns = layer.rgns;
		const size_t cRgns = layer.cRgns;
		assert (cRgns == rgns.size ());

		for (rgns_t::iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			if (g_bStop)
				return lsInterrupted;

			rgn_t & rgn = * iRgn;
			if (rgn.IsDeleted ())
				continue;

			if (! rgn.GetTypeDesc ()) {
				rgn.pTypeDesc = pTypeSet->GetUnknownTD ();
				if (! rgn.IsWTR ())
					ReportWarning (rgn.cBeginPos, "Type is not defined for object.");
			}
			assert (rgn.GetTypeDesc ());

			// Explore elements.
			const size_t cElements = rgn.elements.size ();
			size_t cElementsRest = cElements;
			if (cElements) {
				// Data used to count holes and average element area.
				float fArea = 0;
				size_t cNonHoleElements = 1;

				for (size_t cElement = 0; cElement < cElements; ++ cElement) {
					rgn_element_t & element = rgn.elements [cElement];
					if (element.bDeleted)
						continue;

					points_t & points = element.points;

					if (! rgn.IsWTR ()) {
						// Round the points to grid.
						pTypeSet->pfRoundPoints (* this, element.cLevel, points);

						// Remove repeating points.
						const size_t cWerePoints = points.size ();
						element.RemoveRepeatingPoints ();
						if (points.size () < cWerePoints)
							ReportWarning (element.cFileOffset, "Some points are repeating in the polyline/polygon. The repeating points are removed.");
					}

					size_t cPoints = points.size ();
					if (cPoints > cMaxPointsInElement)
						cMaxPointsInElement = cPoints;

					// Determine the bounding rect.
					for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
						point_t & point = points [cPoint];

						element.rectBound.Extend (point);

						if (g_bStop)
							return lsInterrupted;
					}
					rgn.rectBound.Extend (element.rectBound);

					if (cKind == rkPolyline) {
						// NOTE: for polylines only.
						const bool bIsNotTrack = ! rgn.IsTrack ();

						// Determine length.
						if (element.fLengthOrArea == 0)
							element.fLengthOrArea = GetLength (points);
						// Remove zero-length redundant polylines.
						if (element.fLengthOrArea < 0.5e-5f && bIsNotTrack) {
							ReportWarning (element.cFileOffset, "Polyline element has zero length. It will be ignored.");
							element.bDeleted = true;
						}

						// Remove redundant polylines.
						if (cPoints <= 1 && bIsNotTrack) {
							ReportWarning (element.cFileOffset, "Polyline element has just %d distinguishable point(s). The element will be ignored.", cPoints);
							element.bDeleted = true;
						}
					} else if (cKind == rkPolygon) {
						// NOTE: for polygons only.

						// Remove coinciding first and last points, if any.
						while (cPoints >= 3 && points [0] == points [cPoints - 1]) {
							ReportWarning (element.cFileOffset, "First and last points of polygon are equal. The last point will be ignored.");

							points.pop_back ();
							-- cPoints;
							assert (cPoints == points.size ());
						}
						assert (! (cPoints >= 3 && points [0] == points [points.size () - 1]));

						// Remove redundant polygons.
						if (cPoints <= 2) {
							ReportWarning (element.cFileOffset, "Polygon element has just %d distinguishable point(s). The element will be ignored.", cPoints);
							element.bDeleted = true;
						}

						// Determine area.
						if (element.fLengthOrArea <= 0)
							element.fLengthOrArea = GetArea (points);
						// Remove zero-area redundant polygons.
						if (element.fLengthOrArea < 2.e-11f) {
							ReportWarning (element.cFileOffset, "Polygon element has zero area. It will be ignored.");
							element.bDeleted = true;
						}

						// Count net area of all elements.
						if (element.bHole) {
							bThereAreHoles = true;
							fArea -= element.fLengthOrArea;
						} else {
							++ cNonHoleElements;
							fArea += element.fLengthOrArea;
						}
					}

					if (cPoints > 16384)
						ReportWarning (element.cFileOffset, "Object' element has %d point(s). Under MS Windows 98/ME, only at most 16384 points may be rendered.", cPoints);

					// Check zoom level.
					const size_t cEndLevel = rgn.uchEndLevel != 0 ? rgn.uchEndLevel : element.cLevel;
					for (size_t cLevel = element.cLevel; cLevel <= cEndLevel && cLevel < Levels.size (); ++ cLevel)
						pbRgnsInLevel [cLevel] = true;
					if (element.cLevel >= Levels.size () - 1)
						ReportWarning (element.cFileOffset, "Object' element has incorrect level %d", element.cLevel);

					if (element.bDeleted)
						-- cElementsRest;
				}

				// Get average area of elements.
				if (cKind == rkPolygon)
					rgn.fAveElementArea = fArea/cNonHoleElements;
				else
					rgn.fAveElementArea = 0;
			}

			// Explore origins.
			for (size_t cOrigin = 0; cOrigin < rgn.origins.size (); ++ cOrigin) {
				rgn_origin_t & origin = rgn.origins [cOrigin];
				if (origin.bDeleted)
					continue;

				// Round the point to grid.
				if (! rgn.IsWTR ())
					pTypeSet->pfRoundPoint (* this, origin.cLevel, origin.point);

				// Include origins in the bounding rect.
				rgn.rectBound.Extend (origin.point);

				const size_t cEndLevel = rgn.uchEndLevel != 0 ? rgn.uchEndLevel : origin.cLevel;
				for (size_t cLevel = origin.cLevel; cLevel <= cEndLevel && cLevel < Levels.size (); ++ cLevel)
					pbRgnsInLevel [origin.cLevel] = true;
				if (origin.cLevel >= Levels.size () - 1)
					ReportWarning (origin.cFileOffset, "Object' origin has incorrect level %d.", origin.cLevel);
			}

			rectBound.Extend (rgn.rectBound);

			if (cElementsRest == 0 && rgn.origins.empty ()) {
				ReportWarning (rgn.cBeginPos, "Object does not contain any point. The object will be ignored.");

				rgn.Delete (* this);
			}

			// Check label.
			if (! rgn.strLabel.empty () && Header.CodeSchema == bpsAscii7 && pTypeSet == & g_tsGarmin && ! Is6bitLabelCorrect (rgn.strLabel.c_str ())) {
				Header.CodeSchema = bpsSBCS;
				Header.wCodePage = 1252; // Latin I
				ReportWarning (rgn.cBeginPos, "Label contains symbols not allowed for Garmin's 6-bit coding: %s. The coding schema is switched to 8-bit coding", rgn.strLabel.c_str ());
			}

			// Check phone.
//			if (pTypeSet == & g_tsGarmin && rgn.pExtra && ! rgn.pExtra->strPhone.empty () && ! IsPhoneCorrect (rgn.pExtra->strPhone.c_str ()))
//				ReportWarning (rgn.cBeginPos, "Phone number contains incorrect symbols: %s", rgn.pExtra->strPhone.c_str ());

			// Prepare stuff for the label drawing.
			rgn.fSize2 = 0;
			if (! rgn.strLabel.empty ()) {
				if (cElementsRest)
					rgn.fSize2 = GetRgnSize (rgn);

				const type_desc_t * const pTD = rgn.GetTypeDesc ();
				assert (pTD);
				if (pTD)
					pTD->pfPrepareLabel (rgn);
			}

			// Report progress.
			++ cRgnsProcessed;
			if ((cRgnsProcessed & 0xFF) == 0xFF)
				SetProgressStatus (fast_floor (50 + 50*cRgnsProcessed/cTotalRgns + .5f));
		}
		assert (layer.cRgns == rgns.size ());
	}

	// Sort polygons by fArea.
	layers [rkPolygon].rgns.sort ();//CompareRgnArea ());
	// NOTE: in some cases, MS STL implementation of list<>::sort() loses some of objects!
	// Please use STLPort instead to avoid this bug.
	assert (layers [rkPolygon].cRgns == layers [rkPolygon].rgns.size ());

	// Proceed the attached renderers.
	for (renderers_t::iterator iRenderer = renderers.begin (); iRenderer != renderers.end (); ++ iRenderer)
		rectBound.Extend ((* iRenderer)->rect);

	// NOTE: some map may contain just one point causing rectBound being empty.
	if (rectBound.x0 == rectBound.x1 && rectBound.y0 == rectBound.y1) {
		rectBound.x0 -= 2e-4f;
		rectBound.x1 += 2e-4f;
		rectBound.y0 -= 2e-4f;
		rectBound.y1 += 2e-4f;
	}

	// Check zoom levels.
	if (! Levels.empty ()) {
		for (cLevel = 0; cLevel < Levels.size () - 1; ++ cLevel) {
			if (! pbRgnsInLevel [cLevel])
				ReportWarning ("Zoom level %d is empty.", cLevel);

			if (Levels [cLevel].cZoom >= Levels [cLevel + 1].cZoom)
				ReportWarning ("Zoom%d >= Zoom%d.", cLevel, cLevel + 1);
		}
		if (pbRgnsInLevel [cLevel])
			ReportWarning ("Zoom level %d is not empty.", cLevel);
	} else
		if (! bNoHeader)
			ReportWarning ("Zoom levels are not defined.");

	if (Levels.size () > 0) {
		if (Levels [0].btBits <= 24 && cPrecOrder > 5) {
			ReportWarning ("Input file defines some or all points with excessive precision. Significant digits will be truncated to %d ones.", 5);
		} else if (Levels [0].btBits <= 26 && cPrecOrder > 6) {
			ReportWarning ("Input file defines some or all points with excessive precision. Significant digits will be truncated to %d ones.", 6);
		}
	}

	fCosY = ::cos (rectBound.MeanY ()*c_PI/180.f);

	SetStatusReady ();

	return lsOK;
}

find_info_t map_t::Find (const point_t & _pt, const rgn_t * _pExceptRgn) {
	find_info_t ret;
	
	// The precision of matching in degrees.
	const float c_fE = c_fE_in_pixels/g_kY;

	// The rectangle will be used to match points.
	rect_t rectE;
	rectE.x0 = _pt.x - c_fE/fCosY;
	rectE.x1 = _pt.x + c_fE/fCosY;
	rectE.y0 = _pt.y - c_fE;
	rectE.y1 = _pt.y + c_fE;

	// Visit raster images before objects.
	if (g_bShowAttachments) {
		for (renderers_t::iterator iRenderer = renderers.begin (); iRenderer != renderers.end (); ++ iRenderer) {
			renderer_base_t * const pRenderer = * iRenderer;

			if (! pRenderer->bOverlay && ! pRenderer->bDeleted && pRenderer->bVisible && pRenderer->rect.Contains (_pt))
				ret.pRenderer = pRenderer;
		}
	}

	// NOTE: visit polygons first to make polylines and points to be returned.
	for (int cKind = rkMax - 1; cKind >= 0; -- cKind) {
		layer_t & layer = layers [cKind];
		rgns_t & rgns = layer.rgns;
		for (rgns_t::iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			if (g_bStop)
				return ret;

			rgn_t & rgn = * iRgn;

			if (_pExceptRgn == & rgn)
				continue;

			if (rgn.IsDeleted ())
				continue;

			if (rgn.IsWTR ()) {
				if (! g_bShowAttachments)
					continue;
				if (rgn.pFileRef && ! rgn.pFileRef->bVisible)
					continue;
			}

			if (! rgn.rectBound.Intersects (rectE))
				continue;

			// Match origins.
			for (size_t cOrigin = 0; cOrigin < rgn.origins.size (); ++ cOrigin) {
				const rgn_origin_t & origin = rgn.origins [cOrigin];
				if (origin.bDeleted)
					continue;

				if (! rgn.IsWTR () && ! LevelIsVisible (origin.cLevel, rgn.uchEndLevel))
					continue;

				if (rectE.Contains (origin.point)) {
					ret.pLayer = & layer;
					ret.iRgn = iRgn;
					ret.cElementOrOrigin = cOrigin;
					ret.ptNearest = origin.point;
					continue;
				}
			}
			
			// Match elements.
			for (size_t cElement = 0; cElement < rgn.elements.size (); ++ cElement) {
				const rgn_element_t & element = rgn.elements [cElement]; 
				if (element.bDeleted)
					continue;

				const points_t & points = element.points;
				if (points.empty ())
					continue;

				if (! element.rectBound.Intersects (rectE))
					continue;

				if (! rgn.IsWTR () && ! LevelIsVisible (element.cLevel, rgn.uchEndLevel))
					continue;

				if (rgn.IsPolyline ()) {
					size_t cPoint = -1;
					if (PolylineContainsPt (points, _pt, c_fE, fCosY, false, & ret.ptNearest, & cPoint)) {
						ret.pLayer           = & layer;
						ret.iRgn             = iRgn;
						ret.cElementOrOrigin = cElement;
						ret.cPoint           = cPoint;
						continue;
					}
				} else if (rgn.IsPolygon ()) {
					if (PolygonContainsPt (points, _pt) >= 0) {
						size_t cPoint = -1;
						if (! PolylineContainsPt (points, _pt, c_fE, fCosY, true, & ret.ptNearest, & cPoint))
							ret.ptNearest = _pt;
						ret.pLayer           = & layer;
						ret.iRgn             = iRgn;
						ret.cElementOrOrigin = cElement;
						ret.cPoint           = cPoint;
						continue;
					}
				}
			}
		}
	}

	if (ret.pLayer)
		ret.pRenderer = NULL;

	return ret;
}

template<typename _T>
void _Transform (map_t & _map, const _T & _t) {
	// Update total bounding rectangle.
	_map.rectBound = rect_t ();

	// NOTE: Take the attached images into account but do not transform as reference objects.
	for (renderers_t::iterator iRenderer = _map.renderers.begin (); iRenderer != _map.renderers.end (); ++ iRenderer)
		_map.rectBound.Extend ((* iRenderer)->rect);

	for (size_t cKind = 0; cKind < rkMax; ++ cKind) {
		layer_t & layer = _map.layers [cKind];
		rgns_t & rgns = layer.rgns;
		for (rgns_t::iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			if (g_bStop)
				return;

			rgn_t & rgn = * iRgn;
			if (rgn.IsDeleted ())
				continue;

			if (rgn.IsWTR ()) {
				// NOTE: Tracks and waypoints are not to be transformed because they are reference objects.
				_map.rectBound.Extend (rgn.rectBound);
				continue;
			}

			// Update bounding rectangle of the rgn.
			rgn.rectBound = rect_t ();

			// Update origins.
			for (size_t cOrigin = 0; cOrigin < rgn.origins.size (); ++ cOrigin) {
				rgn_origin_t & origin = rgn.origins [cOrigin];
				if (origin.bDeleted)
					continue;

				_t.ApplyTo (origin.point);

				rgn.rectBound.Extend (origin.point);
			}
			
			// Update elements of the rgn.
			for (size_t cElement = 0; cElement < rgn.elements.size (); ++ cElement) {
				rgn_element_t & element = rgn.elements [cElement];
				if (element.bDeleted)
					continue;

				points_t & points = element.points;
				const size_t cPoints = points.size ();

				element.rectBound = rect_t ();
				for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
					point_t & point = points [cPoint];

					_t.ApplyTo (point);

					element.rectBound.Extend (point);
				}
				rgn.rectBound.Extend (element.rectBound);
			}

			// Update labels' positions.
			if (rgn.dwFlags & rgn_t::fPtLabelDefined)
				_t.ApplyTo (rgn.ptLabel);
			// TODO: fLabelAngle.

			_map.rectBound.Extend (rgn.rectBound);
		}
	}

	// NOTE: some map may contain just one point causing rectBound being empty.
	if (_map.rectBound.x0 == _map.rectBound.x1 && _map.rectBound.y0 == _map.rectBound.y1) {
		_map.rectBound.x0 -= 1e-4f;
		_map.rectBound.x1 += 1e-4f;
		_map.rectBound.y0 -= 1e-4f;
		_map.rectBound.y1 += 1e-4f;
	}
}

void map_t::Transform (const aff_transform_t & _at) {_Transform (* this, _at);}
void map_t::Transform (const q_transform_t   & _qt) {_Transform (* this, _qt);}
# include "MTATransform.h"
void map_t::Transform (const mta_transform_t & _tt) {_Transform (* this, _tt);}

void map_t::TransformPoints (const CTransformationBase & _Transformation) {
	for (size_t cKind = 0; cKind < rkMax; ++ cKind) {
		layer_t & layer = layers [cKind];
		rgns_t & rgns = layer.rgns;
		for (rgns_t::iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			if (g_bStop)
				return;

			rgn_t & rgn = * iRgn;
			if (rgn.IsDeleted ())
				continue;

			// Update origins.
			for (size_t cOrigin = 0; cOrigin < rgn.origins.size (); ++ cOrigin)
				_Transformation.ApplyTo (rgn.origins [cOrigin].point);

			// Update elements of the rgn.
			for (size_t cElement = 0; cElement < rgn.elements.size (); ++ cElement) {
				rgn_element_t & element = rgn.elements [cElement];

				points_t & points = element.points;
				const size_t cPoints = points.size ();
				for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint)
					_Transformation.ApplyTo (points [cPoint]);
			}
		}
	}
}

///////////////////////////////////////////////////////////////////

void map_t::SetRoadID (rgn_t & _rgn) {
	++ dwMaxRoadID;
	_rgn.pExtra->dwRoadID = dwMaxRoadID;
}

void map_t::SetRoadID (rgn_t & _rgn, DWORD _dwRoadID) {
	_rgn.pExtra->dwRoadID = _dwRoadID;

	if (dwMaxRoadID < _dwRoadID)
		dwMaxRoadID = _dwRoadID;
}

void map_t::MakeSureAllRoadIDsAreUnique () {
	std::set<DWORD> RoadIDs;

	rgns_t & polylines = layers [rkPolyline].rgns;
	for (rgns_t::iterator iRgn = polylines.begin (); iRgn != polylines.end (); ++ iRgn) {
		rgn_t & rgn = * iRgn;
		if (rgn.IsDeleted () || rgn.IsWTR ())
			continue;

		bool bHasRoadID = false;
		if (rgn.pExtra && rgn.pExtra->dwRoadID != -1)
			bHasRoadID = true;
		else {
			const size_t cElements = rgn.elements.size ();
			for (size_t cElement = 0; cElement < cElements; ++ cElement) {
				rgn_element_t & element = rgn.elements [cElement];
				if (element.bDeleted)
					continue;
			
				if (element.pExtra == NULL)
					continue;
				point_extras_t & PointExtras = element.pExtra->PointExtras;
				if (HasRGNodes (PointExtras)) {
					bHasRoadID = true;
					break;
				}
			}
		}
		
		if (! bHasRoadID)
			continue;
		DWORD & dwRoadID = rgn.pExtra->dwRoadID;

		// Find free unique value.
		while (true) {
			if (dwRoadID != -1 && RoadIDs.find (dwRoadID) == RoadIDs.end ()) {
				RoadIDs.insert (dwRoadID);
				break;
			}

			++ dwMaxRoadID;
			dwRoadID = dwMaxRoadID;
		}
	}
}